Advent of Code 2020: Day 9

This article features a lot of LaTeX math which is rendered using the JavaScript library MathJax. If you have JavaScript disabled, this article will not render correctly.

In Advent of Code day 9, we are given a list of numbers. The number in position $i$, denoted $x_i$ is valid if it can be expressed as a sum of exactly two of the $k$ previous numbers, i.e. $$ x_i = x_a + x_b,\quad i-1 \leq a, b \leq i-k $$ if this is not possible the number is invalid. The first $k$ numbers are called the preamble and are neither valid nor invalid. Let $k = 5$ while considering the following example input, which I’ve calculated manually in the STATUS column.

INPUT   STATUS
------------------------
35      PREAMBLE
20      PREAMBLE
15      PREAMBLE
25      PREAMBLE
47      PREAMBLE
40      Valid: 25 + 15
62      Valid: 47 + 15
55      Valid: 40 + 15
65      Valid: 40 + 25
95      Valid: 55 + 40
102     Valid: 62 + 40
117     Valid: 55 + 62
150     Valid: 95 + 55
182     Valid: 117 + 65
127     - - INVALID - -
219     Valid: 117 + 102

The real input is much much longer, and the final number in my input is $125438790018542$. Furthermore, we must consider the 25 previous numbers instead i.e. $k = 25$.

Part 1

In part 1 we have to find the first invalid number that appears in the list. For the purpose I made a function which produces every possible sum of two numbers in the list very quickly. This function is the reason I wrote an article on this day. The function is called get_sums() and looks like this:

1
2
3
4
5
6
7
8

import numpy as np
def get_sums(numbers, repeats=False):
    sums = np.add(*np.meshgrid(numbers, numbers))
    sums = np.triu(sums)
    np.fill_diagonal(sums, 0)
    sums = sums.flatten()
    mask = sums != 0
    return sums[mask]

To the untrained and even to me as I am looking back at this, it looks very intimidating. It is way easier to explain by example. For simplicity’s sake, assume a list of 4 numbers from which we want to construct all sums of two of these. We denote the list number: $$ \texttt{number} = \left[ x_1, x_2, x_3, x_4 \right] $$ The numpy command np.meshgrid(number, number) is called in line 3 and will create the 2D grid that has each coordinate in number such that it will create the points denoted $V$ $$ V = \left( (x_1, x_1), (x_1, x_2), (x_1,x_3), \dots (x_2, x_1), (x_2, x_2),\dots (x_4, x_4) \right) $$ In practice it exports the following two arrays $$ A_1 = \begin{bmatrix} x_1 & x_1 & x_1 & x_1 \\ x_2 & x_2 & x_2 & x_2 \\ x_3 & x_3 & x_3 & x_3 \\ x_4 & x_4 & x_4 & x_4 \\ \end{bmatrix} $$ $$ A_2 = \begin{bmatrix} x_1 & x_2 & x_3 & x_4 \\ x_1 & x_2 & x_3 & x_4 \\ x_1 & x_2 & x_3 & x_4 \\ x_1 & x_2 & x_3 & x_4 \\ \end{bmatrix} $$

Notice that $A_1 = A_2^\top$ (transposed) since np.meshgrid receives the same argument for both axes.

Next these to matrices are added using np.add() also on line 3. This produces the matrix we will call $B$ $$ B = A_1 + A_2 = \begin{bmatrix} x_1 + x_1 & x_1 + x_2 & x_1 + x_3 & x_1 + x_4 \\ x_2 + x_1 & x_2 + x_2 & x_2 + x_3 & x_2 + x_4 \\ x_3 + x_1 & x_3 + x_2 & x_3 + x_3 & x_3 + x_4 \\ x_4 + x_1 & x_4 + x_2 & x_4 + x_3 & x_4 + x_4 \\ \end{bmatrix} $$ You may notice that all possible products of the values in numbers are present in this matrix $B$. You may also notice that all the elements except the diagonal elements are present twice. The upper triangular part of the matrix is the same as the lower and as such we merely seperate out the upper triangular part using the function np.triu() on line 4.

Now we notice that the diagonal entries are useless for us in this exercise as they represent adding a number to itself which is not permitted. Therefore we set the diagonals to zero using np.fill_diagonals() on line 5 which does this operation in-place. By doing np.triu() followed by np.fill_diagonals() we acquire the new matrix $C$ $$ C = \begin{bmatrix} 0 & x_1 + x_2 & x_1 + x_3 & x_1 + x_4 \\ 0 & 0 & x_2 + x_3 & x_2 + x_4 \\ 0 & 0 & 0 & x_3 + x_4 \\ 0 & 0 & 0 & 0 \\ \end{bmatrix} $$ The last three lines 6-8 simply flatten this array and mask away all the zeros. This leaves us with all sums of any two numbers in number which was what we wanted from this function anyways.

To get the answer for part 1, I create another function which takes a parsed (the preamble of length $k$) and the unparsed (the rest of the numbers). This function iterates over the unparsed numbers and does the following:

1. Calculates all sums of the parsed numbers using get_sums()
2. If the number is amongst the sums:
   1. The first number is removed in the parsed number
   2. The current number is appended to the parsed numbers
   3. This corresponds to shifting the $k$ numbers ahead
3. If the number is NOT amongst the sum:
   1. Return the number as it is the answer to part 1 The code for this looks like so:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def get_invalid(parsed, unparsed):
    for number in unparsed:
        sums = get_sums(parsed)
        if number not in sums:
            return int(number)
        parsed = np.delete(parsed, 0)
        parsed = np.append(parsed, number)


def part1():
    return get_invalid(*np.split(transmission, [preamble_length]))

Part 2

In part 2 we have to find more than 1 sequential numbers in the list which sum to the answer found in part 1. Here we just iterate over the list without using the complicated function from before, but we do some optimizations to make the progress go faster. The function get_continous_sum_to(target) gets a list of numbers in the list, which sum to target:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def get_continous_sum_to(target):
    for i in range(len(transmission)):
        j = i + 1
        while True:
            cont = transmission[i:j]
            contsum = np.sum(cont)
            if contsum < target:
                j += 1
            elif contsum == target:
                return cont
            else:
                break

The idea is this: We iterate over the list and set the starting number to each number. Then we keep increasing the index j and we check the sum of the list from i to j. If the sum is less than the target, we increase j and try again. If the sum is greater than the target, we cannot start at i and as such we break and try the next i. If the sum is the target, we found the answer. The actual answer to part 2 is to find the sum of the smallest and largest number in this sequence which is simply

1
2
3

def part2():
    cont = get_continous_sum_to(part1())
    return np.min(cont) + np.max(cont)

Overall, day 9 wasn’t too difficult but it was fun creating a broadcasting numpy function capable of producing all two-number sums of a list of numbers. The function is quite fast compared to just iterating over the list twice.

The full code for this day can be found here. The entire repository is available at GitHub.